package class05;

/**
 * 判断满二叉树
 * @author Isamu
 * @create 2024-02-26 10:05
 */
public class Code05_1_IsFBT {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static class Info {
        public int height;
        public int nodes;
        public Info(int height, int nodes) {
            height = this.height;
            nodes = this.nodes;
        }
    }

    public static boolean isFBT(Node head) {
        if (head == null) {
            return true;
        }

        Info data = collectInfo(head);

        // m<<n 代表把数字m在无溢出的前提下乘以2的n次方
        // 右移m>>n 代表把数字m除以2的n次方，原来是正数的还是正数，负数还是负数。注意，如果是单数，也就是二进制末位为1，则结果是将m除以2的n次方的整数商。除以2的1次方
        return data.nodes == (1<<data.height - 1);
    }

    // 收集高度和节点数信息的函数
    public static Info collectInfo(Node x){
        //base case
        if (x == null){
            return new Info(0,0);
        }

        Info leftData = collectInfo(x.left);
        Info rightData = collectInfo(x.right);


        int height = Math.max(leftData.height, rightData.height) + 1;
        int nodes = leftData.nodes + rightData.nodes + 1;


        return new Info(height, nodes);
    }

}
